
package xj.graph2d.graph;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import static xj.graph2d.graph.GraphUtilities.matchEdgeType;

public class GraphAlgorithms {

  static public void breadthFirstSearch(Graph graph, NodeAction action) {
    if (graph != null) {
      Iterator<GraphNode> iter = graph.nodes();
      if (iter.hasNext()) {
	breadthFirstSearch(graph, iter.next(), action);
      }
    }
  }

  static public void breadthFirstSearch(Graph graph, GraphNode src,
					NodeAction action) {
    if (graph != null && src != null) {
      SNode s = null;
      Iterator<GraphNode> niter = graph.nodes();
      while (niter.hasNext()) {
	GraphNode node = niter.next();
	SNode snode = new SNode(node);
	if (node == src) {
	  snode.color = GRAY;
	  snode.d = 0;
	  s = snode;
	}
      }

      if (s != null) {
	if (action != null) {
	  action.visit(s.node);
	}

	List<SNode> q = new LinkedList<SNode>();
	q.add(s);
	while (q.size() > 0) {
	  SNode u = q.get(0);
	  Set<GraphEdge> edges = graph.leavingEdges(u.node);
	  if (edges != null) {
	    Iterator<GraphEdge> eiter = edges.iterator();
	    while (eiter.hasNext()) {
	      GraphEdge e = eiter.next();
	      GraphNode n = e.getDestination();
	      SNode v = (SNode) n.getAux();
	      if (v.color == WHITE) {
		v.color = GRAY;
		if (action != null) {
		  action.visit(v.node);
		}
		v.d = u.d + 1;
		v.p = u;
		q.add(v);
	      }
	    }
	  }
	  u.color = BLACK;
	  q.remove(0);
	}
      }
    }
  }

  /*
   * return true if a back edge is encountered
   */
  static public boolean depthFirstSearch(Graph graph, NodeAction action) {
    return DFS(graph, action, null);
  }

  static private int t = 0;

  static private boolean DFS(Graph graph, NodeAction action, List<GraphNode> flist) {
    boolean hasBackEdge = false;
    if (graph != null) {
      Iterator<GraphNode> niter = graph.nodes();
      List<SNode> l = new ArrayList<SNode>();
      while (niter.hasNext()) {
	GraphNode node = niter.next();
	SNode snode = new SNode(node);
	l.add(snode);
      }

      t = 0;
      Iterator<SNode> iter = l.iterator();
      while (iter.hasNext()) {
	SNode snode = iter.next();
	if (snode.color == WHITE) {
	  hasBackEdge |= DFSVisit(graph, snode, action, flist);
	}
      }
    }
    return hasBackEdge;
  }

  static private boolean DFSVisit(Graph graph, SNode snode, NodeAction action,
				  List<GraphNode> flist) {
    boolean hasBackEdge = false;
    if (snode != null) {
      if (action != null) {
	action.visit(snode.node);
      }
      snode.color = GRAY;
      snode.d = t++;
      Set<GraphEdge> edges = graph.leavingEdges(snode.node);
      if (edges != null) {
	Iterator<GraphEdge> eiter = edges.iterator();
	while (eiter.hasNext()) {
	  GraphEdge e = eiter.next();
	  GraphNode n = e.getDestination();
	  SNode v = (SNode) n.getAux();
	  if (v.color == WHITE) {
	    v.p = snode;
	    hasBackEdge |= DFSVisit(graph, v, action, flist);
	  } else if (v.color == GRAY) {
	    hasBackEdge = true;
	  }
	}
      }
      snode.color = BLACK;
      snode.f = t++;
      if (flist != null) {
	flist.add(0, snode.node);
      }
    }
    return hasBackEdge;
  }

  static public boolean isDAG(Graph graph) {
    return !depthFirstSearch(graph, null);
  }

  static public List<GraphNode> topologicalSort(Graph graph) {
    List<GraphNode> list = new LinkedList<GraphNode>();
    DFS(graph, null, list);
    return list;
  }

  // return the node or an ancestor of the node that is in the set
  static public <N extends GraphNode> 
  N findNodeInSet(N node, Set<N> set) { 
    if (set != null && 
	node != null) {
      while (!set.contains(node)) { 
	Subgraph sg = node.getSubgraph();
	if (sg instanceof HyperGraphNode) { 
	  node = (N) sg;
	} else { 
	  return null;
	}
      }      
    }
    return node;
  }


  /*
   * returns a set of sets that conatain the nodes of the connected
   * components
   */
  static public Set<Set<GraphNode>> getConnectedComponents(Graph graph) {
    return getConnectedComponents(graph, null, -1);
  }

  static public <N extends GraphNode> 
  Set<Set<N>> getConnectedComponents(Graph graph,
				     Set<N> nodeSet, 
				     int edgeType) {
    if (graph != null) {
      DisjointSetForest<N> dsf = new DisjointSetForest<N>();
      Iterator<N> niter;
      if (nodeSet != null) { 
	niter = nodeSet.iterator();
      } else { 
	niter = (Iterator<N>) graph.nodes();
      }
      while (niter.hasNext()) {
	N node = niter.next();
	dsf.makeSet(node);
      }
      Iterator<GraphEdge> eiter = graph.edges();
      while (eiter.hasNext()) {
	GraphEdge edge = eiter.next();
	if (matchEdgeType(edgeType, edge)) {
	  N src = (N) edge.getSource();
	  N des = (N) edge.getDestination();
	  if (dsf.findSet(src) != dsf.findSet(des)) {
	    dsf.union(src, des);
	  }
	}
      }
      return dsf.getTrees();
    }
    return null;
  }

  static public 
  <N extends GraphNode, E extends GraphEdge> Set<Set<N>> 
  getConnectedComponents(Set<N> nodeSet, 
			 Set<E> edgeSet, 
			 int edgeType) {
    if (nodeSet != null && 
	edgeSet != null) {
      DisjointSetForest<N> dsf = new DisjointSetForest<N>();
      Iterator<N> niter = nodeSet.iterator();
      while (niter.hasNext()) {
	N node = niter.next();
	dsf.makeSet(node);
      }
      Iterator<E> eiter = edgeSet.iterator();
      while (eiter.hasNext()) {
	E edge = eiter.next();
	if (matchEdgeType(edgeType, edge)) {
	  N src = (N) edge.getSource();
	  N des = (N) edge.getDestination();
	  src = findNodeInSet(src, nodeSet); 
	  des = findNodeInSet(des, nodeSet);
	  if (dsf.findSet(src) != dsf.findSet(des)) {
	    dsf.union(src, des);
	  }
	}
      }
      return dsf.getTrees();
    }
    return null;
  }

  static public Set getMST_Kruskal(Graph graph) {

    return null;
  }

  static public Set getMST_Prim(Graph graph) {

    return null;
  }

  static public List getShortestPath_Dijkstra(Graph graph) {

    return null;
  }

  private static int WHITE = 0;

  private static int GRAY = 1;

  private static int BLACK = 2;

  private static class SNode {

    SNode(GraphNode node) {
      this.node = node;
      this.color = WHITE;
      this.d = -1;
      this.f = 0;
      this.p = null;
      if (node != null) {
	node.setAux(this);
      }
    }

    GraphNode node;

    int color;

    int d, f;

    SNode p;
  }

  static public class NodeVisitor implements NodeAction {
    public boolean visit(GraphNode node) {
      System.out.println("visit: " + node);
      return false;
    }
  }

  public static void main(String[] args) {
    Graph g1 = new AbstractGraph();
    GraphNode n1 = new AbstractGraphNode("a");
    GraphNode n2 = new AbstractGraphNode("b");
    GraphNode n3 = new AbstractGraphNode("c");
    GraphNode n4 = new AbstractGraphNode("d");
    GraphNode n5 = new AbstractGraphNode("e");
    GraphNode n6 = new AbstractGraphNode("f");
    GraphNode n7 = new AbstractGraphNode("g");
    GraphNode n8 = new AbstractGraphNode("h");
    GraphNode n9 = new AbstractGraphNode("i");
    GraphNode n10 = new AbstractGraphNode("j");
    g1.addNode(n1);
    g1.addNode(n2);
    g1.addNode(n3);
    g1.addNode(n4);
    g1.addNode(n5);
    g1.addNode(n6);
    g1.addNode(n7);
    g1.addNode(n8);
    g1.addNode(n9);
    g1.addNode(n10);
    GraphEdge e1 = new AbstractGraphEdge(n1, n2);
    GraphEdge e2 = new AbstractGraphEdge(n1, n3);
    GraphEdge e3 = new AbstractGraphEdge(n3, n2);
    GraphEdge e4 = new AbstractGraphEdge(n4, n2);
    GraphEdge e5 = new AbstractGraphEdge(n5, n6);
    GraphEdge e6 = new AbstractGraphEdge(n5, n7);
    GraphEdge e7 = new AbstractGraphEdge(n8, n9);
    g1.addEdge(e1);
    g1.addEdge(e2);
    g1.addEdge(e3);
    g1.addEdge(e4);
    g1.addEdge(e5);
    g1.addEdge(e6);
    g1.addEdge(e7);

    System.out.println("Graph g1:");
    System.out.println(g1);
    System.out.println();

    Set<Set<GraphNode>> cc = getConnectedComponents(g1);
    System.out.println("Connected components of g1");
    Iterator<Set<GraphNode>> iter1 = cc.iterator();
    while (iter1.hasNext()) {
      Set<GraphNode> s = iter1.next();
      Iterator<GraphNode> iter2 = s.iterator();
      while (iter2.hasNext()) {
	System.out.print(iter2.next() + " ");
      }
      System.out.println();
    }

    NodeVisitor nv = new NodeVisitor();
    System.out.println();
    System.out.println("breadthFirstSearch g1");
    breadthFirstSearch(g1, n1, nv);
    System.out.println();
    System.out.println("depthFirstSearch g1");
    depthFirstSearch(g1, nv);
    System.out.println();
    System.out.println("isDag(g1): " + isDAG(g1));

    System.out.println();
    System.out.println("toplogical sort g1");
    List<GraphNode> l = topologicalSort(g1);
    for (Iterator<GraphNode> iter = l.iterator(); iter.hasNext();) {
      System.out.println(iter.next());
    }
  }

}
